package com.test.daily.leetcode.y2022.m07.day0702.v01;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;

/**
 * @descriptions:
 * @author: Tom
 * @date: 2022/7/2 上午 08:36
 * @version: 1.0
 */
public class Solution {
    public static class Edge {
        public int from;
        public int to;
        public int available;

        public Edge(int a, int b, int c) {
            this.from = a;
            this.to = b;
            this.available = c;
        }
    }

    public static class Dinic {
        private int N;
        private ArrayList<ArrayList<Integer>> nexts;
        private ArrayList<Edge> edges;
        private int[] depth;
        private int[] cur;

        public Dinic(int nums) {
            // 點的個數, 從1開始算起
            N = nums + 1;
            // 構建出相鄰邊的集合
            nexts = new ArrayList<>();
            for (int i = 0; i <= N; i++) {
                // 把相鄰的邊放置到邊集合
                // 一個點對應一個集合，邊的集合
                nexts.add(new ArrayList<>());
            }
            edges = new ArrayList<>();
            depth = new int[N];
            cur = new int[N];
        }
        public int maxFlow(int s, int t){
            int flow = 0;
            while(bfs(s, t)){
                // 下一次遍歷的時候,
                // 前一次標記了反向邊,重新走
                Arrays.fill(cur, 0);
                flow += dfs(s, t, Integer.MAX_VALUE);
                // 下一次遍歷的時候,高度不再是當前的高度
                // 高度需要重新規劃
                Arrays.fill(depth, 0);
            }
            return flow;
        }
        public void addEdeg(int u, int v, int r) {
            // 原來邊的個數
            int m = edges.size();
            // 添加一條邊
            edges.add(new Edge(u, v, r));
            // u點，增加一條邊m, m為編號
            nexts.get(u).add(m);
            // 添加一條反向邊
            edges.add(new Edge(v, u, 0));
            // v點增加一條反向邊 m+1
            nexts.get(v).add(m + 1);
        }
        // 寬度優先遍歷
        private boolean bfs(int s, int t) {
            LinkedList<Integer> queue = new LinkedList<>();
            queue.addFirst(s);
            boolean[] visited = new boolean[N];
            visited[s] = true;
            while (!queue.isEmpty()) {
                int u = queue.pollLast();
                for (int i = 0; i < nexts.get(u).size(); i++) {
                    Edge e = edges.get(nexts.get(u).get(i));
                    int v = e.to;
                    if (!visited[v] && e.available > 0) {
                        visited[v] = true;
                        depth[v] = depth[u] + 1;
                        if (v == t) {
                            break;
                        }
                        queue.addFirst(v);
                    }
                }
            }
            return visited[t];
        }

        private int dfs(int s, int t, int r) {
            if (s == t || r == 0) {
                return r;
            }
            int f = 0;
            int flow = 0;
            for(; cur[s] < nexts.get(s).size(); cur[s]++){
                int ei = nexts.get(s).get(cur[s]);
                Edge e = edges.get(ei);
                Edge o = edges.get(ei^1);
                // 如果在樹的對應層次上
                // 并且能夠拿到數據流
                if(depth[e.to] == depth[s] + 1 && (f = dfs(e.to, t, Math.min(e.available, r)))!= 0){
                    e.available -= f;
                    o.available += f;
                    flow += f;
                    r -= f; // 如果r此時已經小於0了
                    // 如果 r < 0, 當前就超過任務了,不需要再試
                    if(r < 0){
                        break;
                    }
                }
            }
            return flow;
        }
    }

}
